package com.yangli.leecode.a;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author ly
 * @description https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * @data 2022/4/18
 */
public class LengthOfLongestSubstring {
    public static void main(String[] args){
        LengthOfLongestSubstring lengthOfLongestSubstring = new LengthOfLongestSubstring();
        System.out.println(lengthOfLongestSubstring.lengthOfLongestSubstring("abcabcbb"));
        System.out.println(lengthOfLongestSubstring.lengthOfLongestSubstringN("au"));
        System.out.println(lengthOfLongestSubstring.lengthOfLongestSubstringN3("cdd"));

    }

    //自己写的滑动窗口
    public int lengthOfLongestSubstring(String s){
        int length = s.length();
        if (length == 0) {
            return 0;
        }
        if (length == 1) {
            return 1;
        }
        int slow = 0, fast = 1;
        int res = 0;
        while (fast < length) {
            String window = s.substring(slow, fast);
            if (window.length() > res) {
                res = window.length();
            }
            while (window.contains(String.valueOf(s.charAt(fast))) && slow != fast) {
                ++slow;
                window = s.substring(slow, fast);
            }
            ++fast;
            if (fast == length) {
                window = s.substring(slow, fast);
                if (window.length() > res) {
                    res = window.length();
                }
            }
        }
        return res;
    }

    //官网的滑动窗口
    public int lengthOfLongestSubstring2(String s){
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk < n && !occ.contains(s.charAt(rk))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i);
        }
        return ans;
    }

    // Manacher
    public String longestPalindrome3(String s){
        int start = 0, end = -1;
        StringBuffer t = new StringBuffer("#");
        for (int i = 0; i < s.length(); ++i) {
            t.append(s.charAt(i));
            t.append('#');
        }
        t.append('#');//变成奇数的回型字符串
        s = t.toString();

        List<Integer> arm_len = new ArrayList<Integer>();
        int right = -1, j = -1;
        for (int i = 0; i < s.length(); ++i) {
            int cur_arm_len;
            if (right >= i) {
                int i_sym = j * 2 - i;
                int min_arm_len = Math.min(arm_len.get(i_sym), right - i);
                cur_arm_len = expand(s, i - min_arm_len, i + min_arm_len);
            } else {
                cur_arm_len = expand(s, i, i);
            }
            arm_len.add(cur_arm_len);
            if (i + cur_arm_len > right) {
                j = i;
                right = i + cur_arm_len;
            }
            if (cur_arm_len * 2 + 1 > end - start) {
                start = i - cur_arm_len;
                end = i + cur_arm_len;
            }
        }

        StringBuffer ans = new StringBuffer();
        for (int i = start; i <= end; ++i) {
            if (s.charAt(i) != '#') {
                ans.append(s.charAt(i));
            }
        }
        return ans.toString();
    }

    public int expand(String s, int left, int right){
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            --left;
            ++right;
        }
        return (right - left - 2) / 2;
    }


    //自己写的滑动窗口
    public int lengthOfLongestSubstringN(String s){
        int length = s.length();
        if (length == 0) {
            return 0;
        }
        if (length == 1) {
            return 1;
        }
        int l = 0, r = 0;
        int res = 1;
        while (r < length) {
            if (r == length - 1) {
                res = Math.max(res, r - l + 1);
                break;
            }
            if (l == r) {
                if (s.charAt(l) == s.charAt(r + 1)) {
                    l++;
                }
                r++;
                res = Math.max(res, r - l + 1);
                continue;
            }
            String window = s.substring(l, r + 1);
            if (window.contains(String.valueOf(s.charAt(r + 1)))) {
                l++;
            } else {
                r++;
                res = Math.max(res, r - l + 1);
            }

        }
        return res;
    }

    //自己写的滑动窗口
    public int lengthOfLongestSubstringN2(String s){
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk < n && !occ.contains(s.charAt(rk))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i);
        }
        return ans;
    }

    //1,记录当前字符i上一次出现位置 2，前一位置最初无重复子串 min(1,2)
    public int lengthOfLongestSubstringN3(String s){
        if (s == null || s.length() == 0) {
            return 0;
        }
        int[] chars = new int[26];
        for (int i = 0; i < 26; i++) {
            chars[i] = -1;
        }
        chars[s.charAt(0) - 'a'] = 0;
        int ans = 1;
        for (int i = 1; i < s.length(); i++) {
            int l1 = Math.min(i+1, i - chars[s.charAt(i) - 'a']);
            ans = Math.max(l1, ans);
            chars[s.charAt(i) - 'a'] = i;
        }
        return ans;
    }


}
